package com.example.graph;

/**
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * 此外，你可以假设该网格的四条边均被水包围。
 * <p>
 * 示例 1：
 * 输入：grid = [
 * ['1','1','1','1','0'],
 * ['1','1','0','1','0'],
 * ['1','1','0','0','0'],
 * ['0','0','0','0','0']
 * ]
 * 输出：1
 * <p>
 * 示例 2：
 * 输入：grid = [
 * ['1','1','0','0','0'],
 * ['1','1','0','0','0'],
 * ['0','0','1','0','0'],
 * ['0','0','0','1','1']
 * ]
 * 输出：3
 */
public class UnionFindSetMain {

    // 并查集解决岛屿数量问题(Leetcode200)
    public static void main(String[] args) {

        char[][] grid = {
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}};

        System.out.println(numIslands(grid));


    }

    public static int numIslands(char[][] grid) {
        UnionFindSet uf = new UnionFindSet(grid);

        int[][] directs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[0].length; y++) {
                if (grid[x][y] == '1') {
                    grid[x][y] = 0; // 将"水"标记为陆地(避免重复访问)

                    for (int[] direct : directs) {
                        int newX = x + direct[0];
                        int newY = y + direct[1];
                        if (newX >= 0 && newX < grid.length &&
                                newY >= 0 && newY < grid[0].length &&
                                grid[newX][newY] == '1') {
                            int set1 = uf.hash(x, y, grid[0].length);
                            int set2 = uf.hash(newX, newY, grid[0].length);
                            uf.union(set1, set2);
                        }
                    }
                }
            }
        }
        return uf.getNumSet();
    }

    // 数组实现

    /**
     * 并查集处理一些  不相交集合（Disjoint Sets）  的合并及查询问题。
     * 常用于判断无向图中  连通分量的个数  和  任意两个顶点是否连通
     * 主要包括以下几个操作
     *
     * 1.初始化：把每个元素所在集合初始化为其自身(将每个元素都看成一个个独立的集合)
     * 2.合并（Union）：把两个  不相交的集合  合并成一个集合，通常，合并之前会检查两个元素是否属于同一个集合
     * 3.查询（Find）：查询元素所在的集合（代表节点/代表元），也可以用于判断两个元素是否属于同一个集合
     *
     */
    private static class UnionFindSet {
        /*
         parent[]存储每个节点的父节点，路径压缩之后，存储代表节点。
         哈希表存储结构：key：节点；value：父节点（或代表节点）
         将节点坐标封装后作为parent的索引，对应的值为集合代表节点
         格式如：parent[节点] = 父节点;
         */
        private int[] parent;

        /*
        rank[]按理理说应存储每个子集的层次（秩），
        针对本题，存储每个集合的元素个数哈希表存储结构：key：根节点；value：节点个数
        将根节点坐标封装后作为rank的索引，对应的值为集合节点个数
        格式如：rank[根节点] = 节点个数;
        */
        private int[] rank;

        private int numSet; // 集合(分组)数

        // 完成初始化化工作
        public UnionFindSet(char[][] grid) {
            int rows = grid.length;
            int columns = grid[0].length;
            parent = new int[rows * columns];
            rank = new int[rows * columns];
            numSet = 0;

            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (grid[i][j] == '1') { // 只需要关心"陆地"节点
                        int v = hash(i, j, columns);
                        parent[v] = v; // 将每个节点的父节点置为自己
                        rank[v] = 1;
                        numSet++;
                    }
                }
            }
        }

        /**
         * 查询（Find）：查询元素所在的集合（代表节点/代表元/根节点）
         *
         * 实现方式一：路径压缩
         * 判断当前节点的⽗父节点（即代表节点）是否与⾃自⼰己相同
         * 索引与值相同，意味着该节点的⽗父节点就是⾃自⼰己，即找到了了当前集合的代表节点
         * 反之，递归地查找⽗父节点的⽗父节点，并将其作为当前节点的⽗父节点
         * 最终，每个节点的⽗父节点都将直接指向代表节点，形成⼀一个菊花图。
         *
         * 实现方式二：循环/递归地向上查找父节点，直到找到代表节点
         *
         * @param node
         * @return 元素所在的集合（代表节点/代表元）
         */
        public int find(int node) {
            // 方式一实现:查询并进行路径压缩(只对本次查询的路径进行压缩，其他路径并不会被压缩)
            if (parent[node] != node) {// 父节点不是本身不是根节点
                // 递归地查找父节点的父节点，并将其作为当前节点的父节点
                // 最终，每个节点的父节点都将直接指向代表节点，形成一个菊花图。
                parent[node] = find(parent[node]);
            }
            return parent[node];

            // 方式二实现:循环/递归地向上查找父节点，直到找到代表节点
//            if (parent[node] == node)
//                return node;
//            return find(parent[node]);
        }

        /**
         * 合并:将两个不相交的集合(节点)合并
         * 1.判断两个集合(节点)是否属于同一个集合(判断代表元是否相同)，不同则进行合并
         * 2.按秩(层次)进行合并:将秩小的合并到秩大的集合里
         *   所谓合并也就是将秩小的的代表元变为秩大的代表元
         *
         * 3.集合合并。集合数量减一
         *
         * @param set1
         * @param set2
         */
        public void union(int set1, int set2) {
            int root1 = find(set1);
            int root2 = find(set2);
            if (root1 != root2) { // 两个集合的代表元不同，进行合并
                if (rank[root1] > rank[root2]) {
                    parent[root2] = root1;
                } else if (rank[root1] < rank[root2]) {
                    parent[root1] = root2;
                } else { // 秩相同，合并谁都可以，但是对应的秩要加1
                    parent[root2] = root1;
                    rank[root1]++;
                }

                --numSet;
            }
        }

        public int getNumSet() {
            return numSet;
        }

        /**
         * 将二维数组的坐标转成一维数组下标
         * @param x
         * @param y
         * @param constant
         * @return
         */
        public int hash(int x, int y ,int constant) {
            return x * constant + y;
        }
    }
}
